import matplotlib.pyplot as plt
import numpy as np
from dataclasses import dataclass
from typing import Any

# 边表
@dataclass
class table:
    x: float = 0
    dx:float = 0
    ymax:float = 0
    next_: Any = None

# 算法
def img_fill(img, poly_pt, line):
    # 顶点信息：
    pNum = 0 # 顶点个数
    ymax = ymin = poly_pt[0][1] # y值范围
    for x,y in poly_pt:
        pNum += 1
        if y > ymax: ymax = y
        if y < ymin: ymin = y

    # 建立边表NET
    NET = [None]*(ymax-ymin)
    for y in range(ymin, ymax):     # 按照y进行归类
        for i in range(pNum):       # 保持顶点的顺序
            if poly_pt[i][1] == y:  # 所有y值相等的点
                x = poly_pt[i][0]
                # 顶点在poly_pt内的前后两个顶点（两条连线）：
                pt_pre = poly_pt[i-1]
                pt_next = poly_pt[(i+1)%pNum]
                for pt_ in [pt_next, pt_pre]: # 按照dx大小
                    if pt_[1]>y:     # 确保当前点为y低点
                        # 建立该点的链表，添加到对应位置
                        tab = table(x,(pt_[0]-x)/(pt_[1]-y),
                                    pt_[1], NET[y-ymin])
                        NET[y-ymin] = tab

    # 建立动态边表AET
    AET = []
    for y in range(ymin,ymax):
        # 取出NET到AET
        if NET[y-ymin]:
            while NET[y-ymin]:
                AET.append(NET[y-ymin])
                NET[y-ymin] = NET[y-ymin].next_
                AET[-1].next_ = None
        # 按照x排序, 填充，删除ymax==y的线，x+=dx
            # 若采用链表排序，则可以把AET合并为单链表
        AET.sort(key=lambda tab:tab.x) # 排序
        i = 0; flag = False
        while i<len(AET):
            if AET[i].ymax == y:    # 删除
                AET.pop(i)
                continue
            if flag:  # 填充、x+=dx
                line(img, int(AET[i-1].x), int(AET[i].x), int(y))
                AET[i].x += AET[i].dx
                AET[i-1].x += AET[i-1].dx
                flag = False
            else:
                flag = True
            i += 1
    return img

# 构造图像
img = np.zeros((120,90))
# 多边形坐标
poly_pt = [(20,20),(50,10),(110,30),(110,80),(50,50),(20,70)]


def line(img, x1, x2, y):
    img[x1:x2+1, y] = 255

# 函数调用
img = img_fill(img, poly_pt, line)

# 保存图像
# plt.imsave("填充.png", img, cmap='gray_r')

# 显示图像
fig=plt.figure()
ax = fig.add_subplot(111)
ax.imshow(img, cmap='gray_r')
plt.show()